In a graph database, entities are presented as nodes and relationships between those entities are presented as edges in a view of the relational graph maintained by the graph database. The relational graph may be periodically queried by users via graph queries to learn about the relationships between entities. For example, a user may issue a graph query to find friends or contacts within a social network, the documents that a given user has interacted with, the users that a given document has been accessed by, the entities that satisfy various search criteria, etc. Further, it is not uncommon for a graph query to start at a node, then follow a set of edges to a new set of nodes, and expanding along a new set of edges to yet another set of nodes. In dense graphs traversing all edges of nodes in order to match constraints on these edges may be prohibitively expensive.